#pragma once

#include<algorithm>
#include<assert.h>
#include<iostream>
#include"ReverseIterator.h"

using namespace std;

namespace xyx
{
    
    template<class T>
    struct list_node
    {
        list_node<T>* _prev;
        list_node<T>* _next;
        T _val;

        list_node(const T& val = T())
            :_prev(nullptr)
            ,_next(nullptr)
            ,_val(val)
        {}

    
    };
    
    template<class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef __list_iterator<T,Ref,Ptr> Self;
        typedef list_node<T> Node;
        Node* _node;
        
        __list_iterator(Node* node)
            :_node(node)
        {}
        
        Ref operator*()
        {
            return _node->_val;
        }

       Self operator--(int)
        {
            Self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }
        
       Self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
       Self operator++(int)
        {
            Self tmp(*this);
            _node = _node->_next;
            return tmp;
        }
        
       Self& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        
        bool operator!=(const Self& it) const
        {
            return _node != it._node;
        }
        
        bool operator==(const Self& it) const
        {
            return _node == it._node;
        }
        
        Ptr operator->()
        {
            return &_node->_val;
        }

    };

    template<class T>
    class list
    {
        typedef list_node<T> Node;
    public:
        
        typedef __list_iterator<T,T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;
        typedef ReverseIterator<iterator,T&,T*> reverse_iterator;
        typedef ReverseIterator<iterator,const T&,const T*> const_reverse_iterator;

        reverse_iterator rbegin()
        {
            return iterator(end());
        }

        reverse_iterator rend()
        {
            return iterator(begin());
        }


        const_reverse_iterator rbegin()const
        {
            return iterator(end());
        }

        const_reverse_iterator rend()const
        {
            return iterator(begin());
        }

        iterator begin()
        {
            return _head->_next;
        }
        
        iterator end()
        {
            return _head;
        }
        
        
        const_iterator begin()const
        {
            return _head->_next;
        }
        
        const_iterator end()const
        {
            return _head;
        }


        list()
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
        }

        list(const list<T>& lt)
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
            
            for(auto& e: lt)
            {
                push_back(e);
            }
        }

        void swap(list<T>& lt)
        {
            std::swap(_head, lt._head);
        }

        list<T> operator=(list<T> lt)
        {
            swap(lt);
            return *this;
        }
        
        iterator insert(iterator pos, const T& val)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(val);

            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;
            
            return newnode;
        }

        void push_back(const T& val)
        {
            //Node* tmp = new Node(val);
            //Node* tail = _head->_prev;

            //tail->_next = tmp;
            //tmp->_prev = tail;
            //tmp->_next = _head;
            //_head->_prev = tmp;
            
            insert(end()--,val);
        }

        void push_front(const T& val)
        {
            insert(begin(),val);
        }
        
        iterator erase(iterator pos)
        {
            assert(pos != end());

            Node* cur = pos._node;
            Node* next = cur->_next;
            Node* prev = cur->_prev;

            prev->_next = next;
            next->_prev = prev;

            return next;

            delete cur;
        }
        
        void pop_back()
        {
            erase(--end());
        }

        void pop_front()
        {
            erase(begin());
        }
       
        size_t size()
        {
            size_t sz = 0;
            iterator it = begin();

            while(it != end())
            {
                ++sz;
                ++it;
            }

            return sz;
        }
        
        void clear()
        {
            iterator it = begin();
            while(it != end())
            {
                it = erase(it);
            }
        }
        
        ~list()
        {
            clear();

            delete _head;
            _head = nullptr;
        }

    private:
        Node* _head;
    };

    void Print(const list<int>& lt)
    {
        list<int>::const_iterator it = lt.begin();
        while(it != lt.end())
        {
            cout << *it << " ";
            it++;
        }
        cout << endl;
    }

    void test01()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(3);
        lt.push_back(5);
        lt.push_back(7);
        lt.push_back(9);

        list<int>::iterator it = lt.begin();
        while(it != lt.end())
        {
            cout << *it << " ";
            it++;
        }
        cout << endl;
       
        Print(lt);
    }
    
    void test02()
    {

        xyx::list<int> lt;
        lt.push_back(1);
        lt.push_back(3);
        lt.push_back(5);
        lt.push_back(7);
        lt.push_back(9);
        
        for(auto& e: lt)
        {
            cout << e << " ";
        }
        cout << endl;
        lt.push_front(0);
        
        list<int>::iterator it = lt.begin();
        int n = 3;
        while(n--)
        {
            it++;
        }

        lt.insert(it,30);

        for(auto& e: lt)
        {
            cout << e << " ";
        }
        cout << endl;
        
        lt.erase(lt.begin());
        lt.pop_back();
        lt.pop_front();
        for(auto& e: lt)
        {
            cout << e << " ";
        }
        cout << endl;
        
        lt.clear();

        lt.push_back(1);
        lt.push_back(1);
        lt.push_back(1);


        for(auto& e: lt)
        {
            cout << e << " ";
        }
        cout << endl;
        
        cout << lt.size() << endl;
    }

    void test03()
    {

        xyx::list<int> lt;
        lt.push_back(1);
        lt.push_back(3);
        lt.push_back(5);
        lt.push_back(7);
        lt.push_back(9);
        
        for(auto& e: lt)
        {
            cout << e << " ";
        }
        cout<<endl;

        xyx::list<int> lt1(lt);
        
        for(auto& e: lt)
        {
            cout << e << " ";
        }
        cout<<endl;
    
        
        xyx::list<int> lt2 = lt;
        
        for(auto& e: lt)
        {
            cout << e << " ";
        }
        cout<<endl;
    }
    
    void test4()
    {

        xyx::list<int> lt;
        lt.push_back(1);
        lt.push_back(3);
        lt.push_back(5);
        lt.push_back(7);
        lt.push_back(9);
        
        for(auto& e: lt)
        {
            cout << e << " ";
        }
        cout<<endl;
        
        list<int>::reverse_iterator rit = lt.rbegin();
        while(rit != lt.rend())
        {
            cout << *rit << " ";
            ++rit;
        }
        cout << endl;
    }

} 
